#include <stdio.h>
#include <stdlib.h>
#include <time.h>


void quick_sort(int* arr, int start, int end);

int main(void)
{
    const int n = 4, m = 5;
    int arr[n][m];
    srand(time(NULL));
    int i, j;
    
    /* 给数组赋值 */
    printf("原数组的值为：\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            arr[i][j] = rand() % 1000;
            printf("%-3d ", arr[i][j]);
        }
        printf("\n");
    }
    printf("\n");

    /* 给数组排序 */
    for (i = 0; i < n; i++)
        quick_sort(arr[i], 0, m);


    printf("排序后的数组：\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++)
            printf("%-3d ", arr[i][j]);
        printf("\n");
    }

    printf("\n");
    return 0;
}

/* 快速排序：
 * 采用分治思想，每一次排序选择一个基准值，把小于基准值的数字放在左区间，大于基准值的数字放在右区间
 * 最后基准值放在中间（这个基准值的位置就是最终排好序的位置），
 * 然后分别对左、右区间递归进行快速排序，直到区间内只包含一个数据。
 *
 * 参数start和end含义是区间的两个端点下标，范围是 [start, end)
 */
void quick_sort(int* arr, int start, int end)
{
    /* 实现从小到大排序 */
    if (end - start <= 1) // 递归终止条件 
        return;

    int base = arr[start]; // 选用区间第一个数据当基准值

    int left = start, right = end - 1; // 定义左右两个“指针”
    while (left < right) {
        while (left < right && arr[right] >= base) // 从右往左找第一个比基准值小的数据
            right--;
        arr[left] = arr[right]; // 数据赋值

        while (left < right && arr[left] <= base) // 从左往右找第一个比基准值大的数据
            left++;
        arr[right] = arr[left];
    }
    arr[left] = base; // 最后的位置就是基准值的位置(此时left和right相同)

    quick_sort(arr, start, left); // 递归排序左区间
    quick_sort(arr, left + 1, end); // 递归排序右区间
}


